/**
 * @program: LeetCode
 * @description: LeetCode : 583. 两个字符串的删除操作
 * @author: WXY
 * @create: 2023-01-30 15:47
 * @Version 1.0
 **/
public class Num583_minDistance {
    //方法一：  dp数组中存储需要删除的字符个数
    public static int minDistance(String word1, String word2) {
        char[] str1 = word1.toCharArray();
        char[] str2 = word2.toCharArray();
        int len1 = str1.length;
        int len2 = str2.length;
        //dp[i][j]：以i-1为结尾的字符串word1，和以j-1位结尾的字符串word2，想要达到相等，所需要删除元素的最少次数。
        int[][] dp = new int[len1 + 1][len2 + 1];
        for (int i = 1; i <= len1; i++) dp[i][0] = i;
        for (int j = 1; j <= len2; j++) dp[0][j] = j;
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (str1[i - 1] == str2[j - 1]) {
                    //相同，i-1,和 j-1 就不用管了，只要管前面的就行了，
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    //不相同: 1.将s[i-1]删去（dp[i - 1][j] + 1），
                    //       2.将t[j-1]删除(dp[i][j - 1] + 1),
                    //       3.将s[i-1],t[j-1]都删去(dp[i-1][j-1]+2)，
                    dp[i][j] = Math.min(dp[i - 1][j] + 1, Math.min(dp[i][j - 1] + 1, dp[i - 1][j - 1] + 2));
                }
            }
        }
        return dp[len1][len2];
    }

    //方式二：dp数组中存储word1和Word2中最长相同的子序列的长度，
    public static int minDistance2(String word1, String word2) {
        char[] str1 = word1.toCharArray();
        char[] str2 = word2.toCharArray();
        int len1 = str1.length;
        int len2 = str2.length;
        //dp[i][j]：以i-1为结尾的字符串word1，和以j-1位结尾的字符串word2，最长相同子序列
        int[][] dp = new int[len1 + 1][len2 + 1];
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (str1[i - 1] == str2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return len1 + len2 - 2 * dp[len1][len2];
    }

    public static void main(String[] args) {
        String s = "sea";
        String t = "eat";
        int i = minDistance(s, t);
        System.out.println(i);
    }
}
